量子遥感图像数据分割算法研究

毕思文*，饶思威

中国科学院遥感与数字地球研究所遥感科学国家重点实验室，北京 100101

摘  要：用量子力学的概念和方法来处理遥感图像数据是目前遥感图像处理方法中的新的生长点。在笔者前期提出的量子遥感图像数据的去噪算法和增强算法基础上，作者在本文进一步提出量子遥感图像数据的分割算法。在本文中，作者通过实验验证了量子遥感分割算法对分割精度的提升，通过改进的量子遗传算法自动搜索最优阈值，降低了程序设计的复杂度，并且比传统方法，量子图像分割后的信息熵提高了不少，利用量子遥感图像分割算法实现的图像分割不仅保留了更多的图像信息，而且获得了较为理想的分割效果。

关键词：量子遥感；图像分割；量子遗传算法；最大熵；最优阈值；

DOI: 10.3974/geodp.2019.01.03

1  前言

自从本文第一作者（笔者）在国际上首次提出量子遥感这一概念至今，先后经历了量子遥感理论[1]，量子遥感信息[2]，量子遥感实验[3]，量子遥感成像[4]，量子遥感计算[5]和量子遥感测量等阶段的研究。十几年来，笔者与先后指导的9名研究生成功研究出量子遥感图像数据去噪算法[6]和量子遥感图像数据的增强算法[7]。这二项成果为后续量子图像处理的其它工作（比如：边缘提取，图像分割等）奠定了基础。

遥感图像数据分割是指将遥感图像细分为互不交叉，具有相同特性图像的子区域过程。这些特性可以是像素的灰度值、纹理、颜色，对比度特征等。利用图像分割技术，可有效简化或改变图像的表达形式，便于提取出图像感兴趣的目标，使得图像更容易理解与分析。图像分割的方法主要有阈值法、基于边缘的方法和基于区域的方法等[8]。本文中我们将用阈值法这一通用的方法来进行图像分割。

阈值图像分割法有单阈值图像分割和多阈值图像分割两种。单阈值图像分割，顾名思义，就是寻找一个最优阈值来进行图像分割，进而实现图像二值化，思路简单，对具有明显的双峰灰度直方图的图像特别有效。然而，绝大多数图像特别是遥感图像，图像纹理复杂，边界模糊，由于图像包含的信息量很大，感兴趣的图像目标在背景中显现并不明显。这类的图像直方图会出现多峰和起伏不定的情况。此时，单阈值图像分割已不能反映图像的特点，有必要进行多阈值分割，从而进行后续处理。如何快速有效地寻找到最优分割阈值是多阈值图像分割方法的关键和难点。

常见的阈值法有最大类间方差算法、模糊c-均值算法、双峰法、K-means算法[8]等。近年来，基于最大熵、最大模糊熵准则的图像阈值法取得了比传统方法更理想的结果，引起了人们的极大关注[9–10]。Pun等[11–12]首次提出了基于最大熵准则图像阈值分割方法。Kapur等[13]进一步完善了这种方法。随后，Cheng等[14]将模糊数学理论与最大熵原理相结合，提出了最大模糊熵图像分割方法。Cheng等[8]基于最大模糊熵原理的多阈值图像分割基础上，提出了一种改进的图像多阈值图像分割方法，取得了更好的图像分割效果。这些基于最大熵准则的图像分割方法常采用穷尽搜索法寻找最优多阈值组合。此法虽然能保证得到全局最优解，但是它的程序复杂，计算量大且耗时，所以它的应用限制性很大。

量子遗传算法（Quantum Genetic Algorithm, QGA）是一种将量子力学理论与传统遗传算法(Conventional Genetic Algorithm, CGA)[15–19]相结合的量子智能算法。QGA将子力学中的态矢量表述引入到染色体编码;在演化机制上，利用量子旋转门实现染色体进化。由于引入了量子特性，量子遗传算法较传统遗传算法具有更好的种群多样性、更快的收敛速度和更强的全局搜索能力。它是遗传算法的一种全新改进，其性能远远优于传统遗传算法。为此，本项研究将最大熵准则和量子遗传算法结合起来，提出一种基于量子遗传算法的灰度图像的多阈值分割方法。实验结果表明，该算法提高了图像分割效果的可靠性和稳定性，可以获得优于传统遗传算法的分割结果。

2  量子分割算法

量子遥感图像去噪和量子遥感图像增强都用到了文献[20]和[21]中提及的像素量子比特形式，其大致原理是：假设g(m,n)为分辨率为M×N的原图像，f (m, n)为其归一化图像，可以表示为一个M×N的二维矩阵：

                                    (1)

该表达式的右侧定义了一幅数字图像，矩阵中的每个元素称为图像像素。图像归一化变换一般为:

                                                                              (2)

其中Lmax，Lmin分别表示原图像的最大、最小灰度值；f (m, n)∈[0,1]，表示像素g(m, n)的归一化灰度值。为了实现图像从灰度空间到图像量子空间的映射，借鉴文献[21]中概率统计的观点，定义了如下像素量子比特表达形式:

                                                                                  (3)

其中，|0>和|1>分别表示图像黑点和白点的状态，它们对应基态出现的概率幅分别为, ，并满足归一化条件。分别表示像素为黑色和白色的出现概率。

当g(m, n)=0.5×(Lmax+Lmin)时，表明白色和黑色状态的出现概率相同。而白色与黑色，明与暗都是相对概念，即使具有相同的最大、最小灰度值的不同图像，其灰度直方图的分布不会完全一样。类似的，图像分割也借用了其中量子叠加态的原理，具体定义如下文所示。

2.1  量子染色体编码

在遗传算法中，染色体用确定值来表示，常见的编码方式有二进制、十进制、符号编码等。量子遗传算法的染色体采用随机概率量子比特(qubit)的编码方式表示。一个具有m个量子比特基因表示的量子染色体可以描述为:

                                                                                                                                   (4)

其中|αi|2+|βi|2=1，第i个量子比特基因可由概率幅定义为[αi, βi], i = 1,2,..,m。这种表示方式可表示任意量子叠加态。例如：一个三量子位系统为(上一行表示‘0’的概率幅，下一行表示‘1’的概率幅)：

                                                                                                                                          (5)

则该子系统状态可表示为：

                                                                      (6)

上式结果表明，系统中四种基态出现概率分别为1/8，1/8，3/8，3/8，所以对于式(6)的量子子系统可以同时表示四种状态信息。量子染色体表达的不再是某一确定的信息，而是包含所有可能的信息，对该染色体中的基因任意操作会同时作用于所有可能的状态。从本质上，使得QGA较CGA具有更好的多样性;对于同一优化问题，QGA种群规模比CGA小得多。此外，采用量子染色体编码也可以获得较好的收敛性，随着,或趋于0或1，量子比特编码的染色体将收敛到某确定单一态。

2.2  量子交叉

交叉是遗传算法模仿自然界有性繁殖的基因重组的手段，其操作目的是为了将上一代的优良基因遗传给下一代个体，并进化生成更复杂基因结构的新个体，在一定程度上可避免早熟现象。在CGA中，交叉操作有单点交叉、多点交叉、一致交叉等。

2.3  量子变异

在生物的遗传和进化的过程中，DNA染色体随着细胞的分裂复制有可能会因为某种偶然、特殊因素而导致染色体某些基因发生变异，表现出新的生物性状，产生出新的染色体。变异是指以较小概率，对染色体编码串中的某个或某些基因进行改变，从而生成新个体。量子变异是提高QGA搜索最优解性能的一种有效手段。在量子力学理论中，各个状态间的变换是通过量子门实现的。常见的量子门变换矩阵有：旋转门、异或门、非门和Hadamard门等。量子染色体中的变异操作同样也可以利用量子门来实现，利用最优个体的信息引导种群中染色体进化，提高QGA的收敛性。常见的量子旋转门定义为：

                                                                                                                               (7)

其中：q表示量子旋转门的旋转变异角度，其大小和方向根据一个事先设计的调整策略进行。量子旋转变异操作为：

                                                                                                                      (8)                            

其中[α β]′为基因的量子比特矢量表示。量子旋转变异操作的目的是实现状态间的转移，算法收敛。

2.4  利用最大熵和量子遗传算法实现多阈值分割算法流程

1）初始化进化代数t=0和种群Q(t)；

2）统计图像数据的信息熵；

3）计算适应函数的最佳适应值，统计对应熵值得均值；

4）t=t+1，通过量子变异以及量子旋转门更新种群；

5）如果此时熵值均值达到最大，则输出最佳结果，否则返回第2）步操作；

2.5  量子图像数据分割算法流程图

 

 

图1  利用最大熵和量子遗传算法实现图像数据分割流程图

3  量子图像数据分割算法仿真实验及其结果

在Visual Studio 2013集成开发环境下利用C++与openCV对算法进行实验仿真，并采用OTSU（最大类间方差）算法，K-Means聚类算法，最大熵阈值分割法以及本文的量子分割法（以下简称“毕氏量子分割法”）进行图像数据分割结果图（定性）和数据统计表格（定量）的对比，并且也相应的统计各自的平均运行时间（每一种方法都测试10次）。本文对患者病变的心脏图和机场遥感航拍图进行了图像分割实验，结果如下：

 

      

(a) 原图                           (b) OTSU法

      

(c) K-Means法                        (d) 最大熵阈值分割法

(e) 量子分割方法

图2  四种分割患者心脏图像的方法

 

表1  四种不同的图像分割实验结果评价参数比较

不同的图像分割方法

分割后的图像信息熵

平均运行时间（单位：秒）

OTSU法

0.581895

0.052065

K-Means法

0.553726

0.048037

最大熵阈值法

0.727849

0.062642

毕氏量子分割法

0.921277

0.832738

 

    

(a) 原始图像                           (b) OTSU法

    

    (c) K-Means法                        (d) 最大熵阈值分割法

(e) 量子分割方法

 

图3  四种分割机场航拍图像方法效果对比图

表2  四种不同的图像分割实验结果评价参数比较

不同的图像分割方法

分割后的图像信息熵

平均运行时间（单位：秒）

OTSU法

0.79313

0.066112

K-Means法

0.98953

0.042504

最大熵阈值法

1.23458

0.056347

毕氏量子分割法

1.51822

0.827539

 

实验结果表明，毕氏量子分割法较传统的方法如OTSU法，K-Keans法还有最大熵阈值法有更理想的分割效果，无论是生物学的心脏图还是航拍的遥感图像，分割后的图片纹理更加清晰，结构更加明朗.并且更加重要的是，有表1和表2可以看出，在各种分割方法运行时间相差无几的情况下，毕氏量子分割法比其中信息熵最高的传统方法要高出0.1以上，这无疑验证了本文的量子方法分割出的图像更多的保留了原图像的信息，获得了更好的分割结果。

4  结论

本章在分析了基于最大熵图像分割的基本原理上，提出了一种基于自适应最大熵的多阈值图像分割方法。为了提高多阈值的求解效率,本论文将量子遗传算法应用于遥感图像分割方法中来寻找最优阈值组合，降低了程序设计的复杂度，提高了多阈值图像分割结果的准确性和鲁棒性。在本论文提出的改进量子遗传算法中，为了避免生成无效多阈值解，本论文借鉴了一种二进制值解的有效编码方式[22]，然后,在利用量子旋转门更新过程中，定义了一种自适应旋转角度。实验结果显示，本文提出的基于自适应最大熵的多阈值图像分割方法, 和传统分割算法相比较，能更好的分割出目标。在相同分割阈值个数的情况下，本文方法可以保持更多的图像信息。

5  前景展望

量子遥感成像是目前遥感图像数据处理领域中的一个热门话题。本文提出的毕氏量子分割法是遥感图像数据处理的一个新的生长点。本文对分割遥感图像而进行的多阈值搜索能力，实实在在地提高了图像分割多阈值的自动搜索效率，进而提高了多阈值图像分割结果准确性和稳定性。在图像处理中，其实还存在着大量需要全局寻优的问题，譬如小波去噪中的最优阈值的确定问题以及形态学结构元素的确定问题等。可以尝试将量子遗传算法应用到相关的图像处理方法中。不过值得注意的是，在已有的量子遗传算法中，阈值个数和量子基因位个数的选定是人为设定的，可以采用其它办法来为它们寻找到最优的值。还有染色体的更新、变异通常采用量子旋转门来实现的，也可以考虑将量子计算中的其他量子门应用于进化算法中，或可提高算法的全局寻优效率和性能。

 

参考文献

[1]       毕思文. 量子遥感的概念、框架与内涵探索研究[J]. 红外与毫米波学报, 2003, 22: 1-9.

[2]       毕思文, 韩继霞. 量子遥感信息机理研究[J]. 科技导报, 2006.11.

[3]       毕思文, 韩继霞. 量子遥感的中远红外实验研究[J]. 第十五届全国遥感会议论文集, 2005.8.

[4]       Chen, L., Bi, S. W., Lu, B. Z. Experimental study on the imaging of the squeezed state light at 1064 nm，LASER PHYSICS, 2011.

[5]       毕思文. 量子遥感计算的时间与时间反演算符[J]. 红外与毫米波学报, 2003, 22: 70-75.

[6]       毕思文, 柯余仙. 量子遥感图像数据增强算法研究[J]. 全球变化数据学报, 2018, 2(4): 363-372. DOI:          10.3974/geodp.2018.04.01.

[7]       毕思文, 陈浩. 量子遥感图像数据去噪算法研究[J]. 全球变化数据学报, 2018, 2(3): 260-274. DOI:           10.3974/geodp.2018.03.03.

[8]       徐二静. 基于K-means的遥感图像分割[D]. 乌鲁木齐: 新疆大学, 2014.

[9]       陈明, 王行风. 基于模拟退火改进的多阈值遥感图像分割[J]. 信息系统工程, 2011, 12(8): 73-75

[10]    杨凯, 蒋华伟. 模糊最大熵多阈值分割的改进算法研究[J]. 计算机工程与应用, 2009, 45(32): 174-177.

[11]    Pun T. A new method for grey-level picture thresholding using the entropy of the histogram [J]. Signal Processing, 1980, 2(3): 223-237.

[12]    Pun, T. Entropic thresholding, a new approach. Computer Graphics and Image Processing [J]. 1981, 16(3): 210-239.

[13]    Kapur, J., Sahoo, P, Wong, A. A new method for gray-level picture thresholding using the entropy of the histogram [J]. Computer vision, graphics and image processing, 1985, 29(3): 273-285.

[14]    Cheng, H., Chen, J., Li, J. Threshold selection based on fuzzy C-partition entropy approach. Pattern Recognition [J]. 1998, 31(7): 857-870.

[15]    Han, K. J. Genetic quantum algorithm and its application to combinatorial optimization problem [C]. Proceedings of IEEE International Conference on Evolutionary Computation, 2000: 1354-1360.

[16]    Han, K. J. Quantum-inspired evolutionary algorithm for a class of combinatorial optimization [J]. IEEE Transactions on Evolutionary Computation, 2002, 6(6): 580-593.

[17]    Han, K., Kim J. On setting the parameters of quantum-inspired evolutionary algorithm for practical applications in: Congress on Evolutionary Computation. Canberra, Australia: Citeseer, 2003. 178-184.

[18]    Han, K., Kim J. Quantum-inspired evolutionary algorithms with a new termination criterion, He Gate, and two-phase scheme. IEEE Transactions on Evolutionary Computation, 2004, 8(2): 156-169.

[19]    Han, K, Park, K., Ixe, C., et al. Parallel quantum-inspired genetic algorithm for combinatorial optimization problem [J]. Evolutionary Computation, 2001: 1422-1429.

[20]    Tseng, C. C., Tsung, M. Quantum digital image processing algorithms. In: 16th IPPR Conference on Computer Vision, Graphics and Image Processing (CVGIP 2003). Kinmen: 2003. 827-834.

[21]    许悟生. 基于量子理论的数字图像处理研究[D]. 长沙: 湖南师范大学, 2013.

[22]    付晓薇. 基于量子力学的图像处理方法研究[D]. 武汉: 华中科技大学, 2010.